1552F - Telepanting - CodeForces Solution


binary search data structures dp sortings *2200

Please click on ads to support us..

Python Code:



n = int(input())

X, Y, S = [], [], []
P = 998244353

T = [0]*(n+1)


def findIndex(L, p):
    
    
    n = len(L)
    
    l, r = 0, n
    guess = n // 2
    
    while r > l:
        guess = (r+l) // 2
        
        if L[guess] <= p:
            l = guess + 1
            
        elif L[guess] > p:
            r = guess
    
    return l


for i in range(n):
    xi, yi, si = map(int, input().split())
    
    X.append(xi)
    Y.append(yi)
    S.append(si)
    
    j = findIndex(X, yi)
        
    T[i+1] = (xi-yi + 2*T[i] - T[j]) % P

xn = X[-1]
total = xn+1
Test = [0]*n

for i in range(n):
    si = S[i]
    
        
    total += (T[i+1]-T[i]) * si
    total %= P
    

print(total)


Comments

Submit
0 Comments
More Questions

1475A - Odd Divisor
1454B - Unique Bid Auction
978C - Letters
501B - Misha and Changing Handles
1496A - Split it
1666L - Labyrinth
1294B - Collecting Packages
1642B - Power Walking
1424M - Ancient Language
600C - Make Palindrome
1669D - Colorful Stamp
1669B - Triple
1669A - Division
1669H - Maximal AND
1669E - 2-Letter Strings
483A - Counterexample
3C - Tic-tac-toe
1669F - Eating Candies
1323B - Count Subrectangles
991C - Candies
1463A - Dungeon
1671D - Insert a Progression
1671A - String Building
1671B - Consecutive Points Segment
1671C - Dolce Vita
1669G - Fall Down
4D - Mysterious Present
1316B - String Modification
1204A - BowWow and the Timetable
508B - Anton and currency you all know